//
// Created by jizhe hu on 2024/2/21.
//

#ifndef LEETCODE_DP_H
#define LEETCODE_DP_H

#include <vector>
#include <iostream>
#include <functional>

using namespace std;

//! 509. 斐波那契数
int fib(int n) {
    int prev = 0, last = 1;
    for (int i=0; i<n-1; i++) {
        int tmp = last;
        last += prev;
        prev = tmp;
    }
    return last;
}

//! 70.爬楼梯
int climbStairs(int n) {
// dp[n] = dp[n-1] + dp[n-2]
    if (n <= 3) return n;

    int prev = 1, last = 2, res = 3;
    for (int i=0; i<n-3; i++) {
        prev = last;
        last = res;
        res = prev + last;
    }
    return res;
}

//! 746. 使用最小花费爬楼梯
int minCostClimbingStairs(vector<int>& cost) {
    // dp[n] = min(dp[n-1] + cost[n-1], dp[n-2] + cost[n-2])
    int n = cost.size();
    if (n < 3) return min(cost[0], cost[1]);
    int prev = cost[0], last = min(cost[0], cost[1]), res = min(cost[1], last + cost[2]);
    for (int i=4; i<=n; i++) {
        prev = last;
        last = res;
        res = min(prev + cost[i-2], last + cost[i-1]);
    }
    return res;
}

//! 62. 不同路径
int uniquePaths(int m, int n) {
    // dp[i][j] = dp[i-1][j] + dp[i][j-1]
    vector<vector<int>> dp(m, vector(n,0));
    for (int i=0; i<n; i++) {
        dp[0][i] = 1;
    }
    for (int i=0; i<m; i++) {
        dp[i][0] = 1;
    }
    for (int i=1; i<m; i++) {
        for (int j=1; j<n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

//! 62. 不同路径（排列组合）
int uniquePaths_(int m, int n) {
    int count = m - 1;
    long long upper = 1, down = m - 1;
    int t = m + n - 2;
    while(count--) {
        upper *= t;
        t--;
        while(down != 0 && upper % down == 0) {
            upper /= down;
            down--;
        }
    }
    return upper;
}

//! 63. 不同路径 II
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();

    vector<vector<int>> dp(m, vector(n,0));

    for (int i=0; i<n && obstacleGrid[0][i] == 0; i++) {
        dp[0][i] = 1;

    }
    for (int i=0; i<m && obstacleGrid[i][0] == 0; i++) {
        dp[i][0] = 1;
    }
    for (int i=1; i<m; i++) {
        for (int j=1; j<n; j++) {
            if(obstacleGrid[i][j] == 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[m-1][n-1];
}

//! 343. 整数拆分
int integerBreak(int n) {
    if (n <= 3) return n - 1;
    vector dp(n+1, 0);
    dp[2] = 2;
    dp[3] = 3;
    dp[4] = 4;

    for (int i=5; i<=n; i++) {
        for (int j=1; j <= i/2; j++) {
            dp[i] = max(dp[i], dp[i-j] * dp[j]);
        }
    }

    return dp[n];
}

//! 96. 不同的二叉搜索树
int numTrees(int n) {
    vector<int> dp(n+1);
    dp[0] = 1;
    for (int i=1; i<=n; i++) {
        dp[i] = 0;
        int prev = 0;
        int last = i-1;
        while(last >= prev) {
            if (last > prev) {
                dp[i] += (dp[prev] * dp[last] * 2);
            } else {
                dp[i] += (dp[prev] * dp[last]);
            }
            prev++;
            last--;
        }
    }
    return dp[n];
}

//! 1049. 最后一块石头的重量 II
int lastStoneWeightII(vector<int>& stones) {
    if(stones.size() == 1) return stones[0];
    int sum = 0;
    for (auto num : stones) {
        sum += num;
    }
    vector<int> dp(sum + 1, 0);

    for (int i=0; i<stones.size(); i++) {
        for (int j=sum / 2; j>=0; j--) {
            if(j >= stones[i]) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
    }

    return sum - dp[sum / 2] * 2;
}

//! 494. 目标和
int findTargetSumWays(vector<int>& nums, int target) {
    int sum = 0;
    for (auto num : nums) {
        sum += num;
    }
    if((sum + target) % 2 == 1) return 0;
    int find_target = (sum + target) / 2;
    if(find_target < 0) find_target = sum - find_target;
    vector<int> dp(find_target + 1, 0);
    dp[0] = 1;

    for (int i=0; i<nums.size(); i++) {
        for (int j=find_target; j>=0; j--) {
            if(j >= nums[i]) {
                dp[j] += dp[j - nums[i]];
            }
        }
    }

    return dp.back();
}

//! 474. 一和零
int findMaxForm(vector<string>& strs, int m, int n) {
    int val_m, val_n;
    function<void(string, int&, int&)> count01 = [](string str, int& m, int& n){
        m = n = 0;
        for(auto s : str) {
            if(s == '0') {
                m++;
            } else if(s == '1') {
                n++;
            }
        }
        return ;
    };

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for(int i=0; i<strs.size(); i++) {
        count01(strs[i], val_m, val_n);
        for(int j=m; j>=0; j--) {
            for(int k=n; k>=0; k--) {
                if(j >= val_m && k >= val_n) {
                    dp[j][k] = max(dp[j][k], dp[j - val_m][k - val_n] + 1);
                }
            }
        }
    }

    return dp[m][n];
}

// 先遍历物品，在遍历背包
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

//! 518. 零钱兑换 II
int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;

    for(int i=0; i<coins.size(); i++) {
        for(int j=coins[i]; j<=amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }

    return dp.back();
}

//! 377. 组合总和 Ⅳ
int combinationSum4(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;

    for(int j=1; j<=target; j++) {
        for(int i=0; i<nums.size(); i++) {
            if(j >= nums[i]) {
                dp[j] += dp[j - nums[i]];
            }
        }

    }

    return dp.back();
}

// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
int climbStairs(int m, int n) {
    vector<int> dp(n + 1, 0);

    for(int j=1; j<=n; j++) {
        for(int i=1; i<=m; i++) {
            if(j >= i) {
                dp[j] += dp[j - i];
            }
        }
    }
    return dp.back();
}

//! 322. 零钱兑换
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for(int i=0; i<coins.size(); i++) {
        for(int j=coins[i]; j<=amount; j++) {
            if(dp[j - coins[i]] != INT_MAX) {
                dp[j] = min(dp[j], 1 + dp[j - coins[i]]);
            }
        }
    }
    return dp.back() == INT_MAX ? -1 : dp.back();
}

//! 279. 完全平方数
int numSquares(int n) {
    vector<int> dp(n+1, INT_MAX);
    dp[0] = 0;

    int sz = 1;
    for(sz = 1; (sz * sz) < n; sz ++) {

    }

    if(sz * sz == n) return 1;

    for(int i=1; i<sz; i++) {
        for(int j=(i*i); j<=n; j++) {
            if(dp[j - i * i] != INT_MAX) {
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
    }

    return dp.back() == INT_MAX ? 0 : dp.back();
}

//! 139. 单词拆分
bool wordBreak(string s, vector<string>& wordDict) {
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;

    for(int i=1; i<=s.size(); i++) {
        for(int j=0; j<i; j++) {
            string str = s.substr(j, i-j);
            if(find(wordDict.begin(), wordDict.end(), str) != wordDict.end() && dp[j]) {
                dp[i] = true;
            }
        }
    }
    return dp.back();
}

//! 300. 最长递增子序列
int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    int res = 0;

    for(int i=0; i<nums.size(); i++) {
        for(int j=0; j<i; j++) {
            if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
        res = max(res, dp[i]);
    }
    return res;
}

//! 674. 最长连续递增序列
int findLengthOfLCIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    int res = 1;
    for(int i=1; i<nums.size(); i++) {
        if(nums[i] > nums[i-1]) dp[i] = max(dp[i], dp[i-1] + 1);
        res = max(res, dp[i]);
    }
    return res;
}


#endif //LEETCODE_DP_H
